The languages accepted by finite automata are precisely the languages denotedby regular expressions. In contrast, finite automata may exhibit behavioursthat cannot be described by regular expressions up to bisimilarity. In thispaper, we consider extensions of the theory of regular expressions with variousforms of parallel composition and study the effect on expressiveness. First weprove that adding pure interleaving to the theory of regular expressionsstrictly increases its expressiveness up to bisimilarity. Then, we prove thatreplacing the operation for pure interleaving by ACP-style parallel compositiongives a further increase in expressiveness. Finally, we prove that the theoryof regular expressions with ACP-style parallel composition and encapsulation isexpressive enough to express all finite automata up to bisimilarity. Ourresults extend the expressiveness results obtained by Bergstra, Bethke andPonse for process algebras with (the binary variant of) Kleene's staroperation.
展开▼
